package exp6;

import exp4.AvlTree;
import exp5.QuadraticProbingHashTable;
import exp5.SeparateChainingHashTable;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;

/**
 * Function:
 * Editor: HexWarrior6
 * Date: 2023/11/29 10:14
 */
public class Search {
    public static void main(String[] args) {
        final int N = (int) 500000;
        ArrayList<Integer> arr = new ArrayList<>();
        Random rand = new Random();
        HashSet<Integer> flag = new HashSet<>();
        for (int i = 0; i < N; i++) {
            int n = rand.nextInt(N);
            if (flag.contains(n)) {
                i--;
            } else {
                arr.add(n);
                flag.add(n);
            }
        }

        long stime = System.nanoTime();
        System.out.println("sequentialSearch: " + sequentialSearch(arr, N / 2));
        long etime = System.nanoTime();
        System.out.println("spend: " + (etime - stime));
        System.out.println();


        ArrayList<Integer> barr = (ArrayList<Integer>) arr.clone();
        stime = System.nanoTime();
        Collections.sort(barr);
        System.out.println("binarySearch: " + binarySearch(barr, N / 2));
        etime = System.nanoTime();
        System.out.println("spend: " + (etime - stime));
        System.out.println();


        AvlTree<Integer> tree = new AvlTree<>();
        for (int i = 0; i < arr.size(); i++) {
            tree.insert(arr.get(i));
        }
        stime = System.nanoTime();
        System.out.println("AVLtreeSearch: " + tree.search(N / 2));
        etime = System.nanoTime();
        System.out.println("spend: " + (etime - stime));
        System.out.println();


        SeparateChainingHashTable<Integer> hashTable1 = new SeparateChainingHashTable<>();
        for (int i = 0; i < arr.size(); i++) {
            hashTable1.insert(arr.get(i));
        }
        stime = System.nanoTime();
        System.out.println("sepatateHashTableSearch: " + hashTable1.contains(N / 2));
        etime = System.nanoTime();
        System.out.println("spend: " + (etime - stime));
        System.out.println();


        QuadraticProbingHashTable<Integer> hashTable2 = new QuadraticProbingHashTable<>();
        for (int i = 0; i < arr.size(); i++) {
            hashTable2.insert(arr.get(i));
        }
        stime = System.nanoTime();
        System.out.println("addressingHashTableSearch: " + hashTable2.contains(N / 2));
        etime = System.nanoTime();
        System.out.println("spend: " + (etime - stime));
    }

    public static int sequentialSearch(ArrayList<Integer> arr, int aim) {
        for (int i = 0; i < arr.size(); i++) {
            if (arr.get(i) == aim) {
                return i;
            }
        }
        return -1;
    }

    public static int binarySearch(ArrayList<Integer> arr, int key) {
        int low = 0;
        int high = arr.size() - 1;
        int middle = 0;            //定义middle

        if (key < arr.get(low) || key > arr.get(high) || low > high) {
            return -1;
        }

        while (low <= high) {
            middle = (low + high) / 2;
            if (arr.get(middle) > key) {
                //比关键字大则关键字在左区域
                high = middle - 1;
            } else if (arr.get(middle) < key) {
                //比关键字小则关键字在右区域
                low = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;        //最后仍然没有找到，则返回-1
    }
}